package sort;

import java.util.*;

public class NodeTest {

    //         10
    //    4         6
    //2      5   3     7
    public static void main(String[] args) {
        Node root = new Node(10);
        Node l1 = new Node(4);
        Node l1l = new Node(2);
        Node l1r = new Node(5);
        Node r1 = new Node(6);
        Node r1l = new Node(3);
        Node r1r = new Node(7);

        l1.left = l1l;
        l1.right = l1r;

        r1.left = r1l;
        r1.right = r1r;

        root.left = l1;
        root.right = r1;

        List<List<Integer>> res = StackTraverse.levelOrder(root);
        System.out.println(Arrays.toString(res.toArray()));
    }


    //前序遍历
    public static void preOrderTraveralWithStack(Node root) {
        Stack<Node> stack = new Stack<>();
        Node treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                System.out.println(treeNode.val);
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                treeNode = treeNode.right;
            }
        }
    }

    public static void middleOrderTraversal(Node root) {
        Stack<Node> stack = new Stack<>();
        Node treeNode = root;
        while (treeNode != null || !stack.isEmpty()) {
            while (treeNode != null) {
                stack.push(treeNode);
                treeNode = treeNode.left;
            }
            if (!stack.isEmpty()) {
                treeNode = stack.pop();
                System.out.println(treeNode.val);
                treeNode = treeNode.right;
            }
        }
    }

    public static class StackTraverse{
        public static List<Integer> preOrder(Node root){
            List<Integer> res = new ArrayList<>();
            Stack<Node> stack = new Stack<>();
            while (root != null || !stack.empty()){
                while(root != null){
                    res.add(root.val);
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                root = root.right;
            }
            return res;
        }

        public static List<Integer> middleOrder(Node root){
            List<Integer> res = new ArrayList<>();
            Stack<Node> stack = new Stack<>();
            while(root != null || !stack.empty()){
                while(root != null){
                    stack.push(root);
                    root = root.left;
                }
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
            return res;
        }

        /**
         *前序遍历 root -> left -> right
         * 后序遍历 left -> right -> root
         * 修改前序遍历 root -> right -> left
         * 那么这个顺序就和后序遍历正好相反
         * @param root
         * @return
         */
        public static List<Integer> postOrder(Node root){
            LinkedList<Integer> res = new LinkedList<>();
            Stack<Node> stack = new Stack<>();
            while (root != null || !stack.empty()){
                while (root != null){
                    res.addFirst(root.val);
                    stack.push(root);
                    root = root.right;
                }
                root = stack.pop();
                root = root.left;
            }
            return res;
        }

        public static List<List<Integer>> levelOrder(Node root) {
            List<List<Integer>> res = new LinkedList<>();
            //用来存当层的结点
            Queue<Node> queue = new LinkedList<>();
            if(root == null) return res;
            queue.offer(root);
            while (!queue.isEmpty()){
                int size = queue.size();
                List<Integer> tmp = new ArrayList<>();
                //遍历当层结点
                for (int i = 0; i < size; i++) {
                    Node node = queue.poll();
                    tmp.add(node.val);
                    if(node.left != null){
                        queue.offer(node.left);
                    }
                    if(node.right != null){
                        queue.offer(node.right);
                    }
                }
                if(tmp.size() > 0){
                    res.add(tmp);
                }
            }
            return res;
        }
    }

    public static class RecursionTraverse{

        public static void preOrderRecursion(Node root){
            if(root == null) return;

            System.out.println(root.val);
            preOrderRecursion(root.left);
            preOrderRecursion(root.right);
        }

        public static void middleOrderRecursion(Node root){
            if(root == null) return;

            middleOrderRecursion(root.left);
            System.out.println(root.val);
            middleOrderRecursion(root.right);
        }

        public static void lastOrderRecursion(Node root){
            if(root == null) return;

            lastOrderRecursion(root.left);
            lastOrderRecursion(root.right);
            System.out.println(root.val);
        }
    }
}
